/*
 * 6.1.cpp 1928
 *
 *  Created on: 2012-5-18
 *      Author: jawinton
 */

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>

using namespace std;

#define SIZE 51

int M, N, K;

struct Pos {
	int x;
	int y;
};

struct Nut {
	Pos pos;
	int num;
};

Nut field[SIZE*SIZE];

int compare (const void * a, const void * b) {
  return ( ((Nut*)b)->num - ((Nut*)a)->num );
}

int main (void) {
	int n;
	cin >> n;
	if (n<1 || n>20) return -1;
	while (n--) {
		cin >> M >> N >> K;
		if (M<1 || N<1 || M>50 || N>50) return -1;
		if (K<0 || K>20000) return -1;
		for (int i=0; i<M; i++) {
			for (int j=0; j<N; j++) {
				cin >> field[N*i+j].num;
				if (field[N*i+j].num > 3000) return -1;
				field[N*i+j].pos.x = i;
				field[N*i+j].pos.y = j;
			}
		}
		qsort(field, M*N, sizeof(Nut), compare);
		int leftTime = K, totalNuts = 0;
		Pos curPos;
		Nut maxNut;
		int i = 0;
		while (leftTime > 0 && i<M*N) {
			maxNut =field[i];
			if (i == 0) {
				curPos.x = -1;
				curPos.y = maxNut.pos.y;
			}
			if (maxNut.num == 0) break;
			int needTime = 0, usedTime = 0;
			needTime += (abs(curPos.x-maxNut.pos.x) + abs(curPos.y-maxNut.pos.y));
			needTime ++;
			usedTime = needTime;
			needTime += (maxNut.pos.y + 1);
			if (needTime < leftTime) {
				curPos = maxNut.pos;
				totalNuts += maxNut.num;
				leftTime -= usedTime;
			}
			i++;
		}
		cout << totalNuts << endl;
	}
	return 0;
}
